题意
$n$种颜色每种各$k$个球排列，每种颜色最左边的球染成白色，问不同颜色序列数
$n,k\leq 2000$
题解
这道题目的idea就是把每种颜色的后k-1个球一起算
令$f_{i,j}$为已经出现了i种颜色，有j个白球的方案，容易知道$i\leq j$
下一个放白球：$f_{i,j}+=f_{i,j-1}$
下一个放别的颜色：$f_{i,j}+=f_{i-1,j}\cdot (n-i+1)\cdot S$
我们来看在$f_{i-1,j}$的时候后面还有几个位置：$n\cdot k-(i-1)\cdot (k-1)-j$,那么$S=C_{pos-1}^{k-1}$
调试记录
算位置i没-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <cstdio>
#define LL long long
const int maxn = 4e6 + 5;
const int mo = 1e9 + 7;
using namespace std;
LL f[2005][2005], fac[maxn], inv[maxn];
LL C(int n, int m){
if (m == 0 || m == n) return 1;
if (m > n) return 0;
return fac[n] * inv[n - m] % mo * inv[m] % mo;
}
LL pow(LL x, int t){
LL res = 1; x %= mo;
while (t > 0){
if (t & 1) res = res * x % mo;
x = x * x % mo;
t >>= 1;
}
return res;
}
int n, k;
int main(){
scanf("%d%d", &n, &k);
if (k == 1){
puts("1");
return 0;
}
fac[0] = 1;
for (int i = 1; i <= n * k; i++) fac[i] = fac[i - 1] * i % mo;
inv[n * k] = pow(fac[n * k], mo - 2);
for (int i = n * k - 1; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % mo;
for (int i = 0; i <= n; i++)
for (int j = i; j <= n; j++){
if (i == 0 && j == 0) f[i][j] = 1;
if (j != 0) f[i][j] = (f[i][j] + f[i][j - 1]) % mo;
if (i != 0) f[i][j] = (f[i][j] + f[i - 1][j] * (n - i + 1) % mo * C(n * k - (i - 1) * (k - 1) - j - 1, k - 2) % mo) % mo;
}
printf("%lld\n", f[n][n]);
return 0;
}
|